package club.xiaojiawei.binarytree;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/19/22 6:56 PM
 * @question 450. 删除二叉搜索树中的节点
 * @description 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
 * 一般来说，删除节点可分为两个步骤：
 * 首先找到需要删除的节点；
 * 如果找到了，删除它。
 */
public class DeleteNode450 {

    public static void main(String[] args) {
        DeleteNode450 test = new DeleteNode450();
        TreeNode root = new TreeNode(2, new TreeNode(1), null);
        TreeNode result = test.deleteNode(root, 2);
        System.out.println(result);
    }

    /**
     * 模拟
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null){
            return null;
        }
        TreeNode treeNode = new TreeNode(Integer.MIN_VALUE);
        treeNode.right = root;
        TreeNode current = treeNode;
        while (true){
            if (key > current.val){
                if (current.right != null){
                    if (current.right.val == key){
                        current.right = deleteNode(current.right);
                        return treeNode.right;
                    }
                    current = current.right;
                }else {
                    return treeNode.right;
                }
            }else if (key < current.val){
                if (current.left != null){
                    if (current.left.val == key){
                        current.left = deleteNode(current.left);
                        return treeNode.right;
                    }
                    current = current.left;
                }else {
                    return treeNode.right;
                }
            }
        }
    }

    public TreeNode deleteNode(TreeNode root){
        TreeNode pre = null;
        TreeNode current;
        if ((current = root.right) != null){
            while (current.left != null){
                pre = current;
                current = current.left;
            }
            if (pre != null){
                pre.left = current.right;
                current.left = root.left;
                current.right = root.right;
            }else {
                current.left = root.left;
            }
            return current;
        }else if ((current = root.left) != null){
            while (current.right != null){
                pre = current;
                current = current.right;
            }
            if (pre != null){
                pre.right = current.left;
                current.left = root.left;
            }
            return current;
        }
        return null;
    }


    /**
     * 官方-递归
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode2(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        }else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        }else {
            if (root.left == null && root.right == null) {
                root = null;
            }else if (root.right != null) {
//                把右子树里最小值节点的值赋给当前节点
                root.val = successor(root);
//                然后在右子树中删除最小值节点
                root.right = deleteNode(root.right, root.val);
            }else {
                root.val = predecessor(root);
                root.left = deleteNode(root.left, root.val);
            }
        }
        return root;
    }

    public int successor(TreeNode root) {
        root = root.right;
        while (root.left != null) {
            root = root.left;
        }
        return root.val;
    }

    public int predecessor(TreeNode root) {
        root = root.left;
        while (root.right != null) {
            root = root.right;
        }
        return root.val;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
